/**************************************************************************************************
	$Header: /pub/cvsroot/mydns/src/mydns/sort.c,v 1.5 2002/08/23 01:00:38 bboy Exp $
	sort.c: Record sorting for load balancing and round robin.

	Copyright (C) 2002  Don Moore <bboy@bboy.net>

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at Your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
**************************************************************************************************/

#include "named.h"


#define RRLIST_SORT_CMP(n1,n2) ((n1)->sort - (n2)->sort)

//	( ((n1)->sort - (n2)->sort) ? ((n1)->sort - (n2)->sort) : strcasecmp((n1)->name, (n2)->name) )

#define RR_IS_ADDR(R) \
			(((MYDNS_RR *)(R)->rr)->type == DNS_T_A || ((MYDNS_RR *)(R)->rr)->type == DNS_T_AAAA)
#define RR_IS_MX(R) \
			(((MYDNS_RR *)(R)->rr)->type == DNS_T_MX)


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	RRLIST_SORT
	Sorts the contents of an RRLIST according to the value(s) in 'sort'
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static RR *
rrlist_sort(RR *head)
{
	RR	*low, *high, *current, *pivot, *temp;
	int result;

	if (!head)
		return (NULL);
	current = head;
	do
	{
		current = current->next;
		if (!current)
			return (head);
	} while (!(result = RRLIST_SORT_CMP(head,current)));

	if (result > 0)
		pivot = current;
	else
		pivot = head;
	low = high = NULL;
	current = head;
	while (current)
	{
		temp = current->next;
		if (RRLIST_SORT_CMP(pivot,current) < 0)
		{
			current->next = high;
			high = current;
		}
		else
		{
			current->next = low;
			low = current;
		}
		current = temp;
	}
	low  = rrlist_sort(low);
	high = rrlist_sort(high);
	current = temp = low;
	while (1)
	{
		current = current->next;
		if (!current)
			break;
		temp = current;
	}
	temp->next = high;
	return low;
}
/*--- rrlist_sort() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	LOAD_BALANCE
	Use the 'aux' value to weight the choice of first nameserver.  'aux' should be 0-10.
	'0' means "never list first", 10 means "list first most frequently".

	This is a pretty crummy algorithm.
	I welcome more efficient and/or just plain better suggestions.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static inline void
load_balance(t, rrlist)
	TASK *t;
	RRLIST *rrlist;
{
	register RR *node;
	register int max = 1, num;

	/* Assign a range of numbers to each address record */
	for (node = rrlist->head; node; node = node->next)
	{
		register MYDNS_RR *rr = (MYDNS_RR *)node->rr;

		if (node->rrtype != DNS_RRTYPE_RR || !RR_IS_ADDR(node))
			continue;
		if (rr->aux > 10)
			rr->aux = 10;

		if (rr->aux == 10)
			node->lb_low = node->lb_high = 0;
		else
		{
			node->lb_low = max;
			node->lb_high = node->lb_low + (10 - rr->aux) * (10 - rr->aux) * (rrlist->highest_addr_aux - rr->aux) + 100;
			max = node->lb_high + 1;
		}
	}

	/* Now get a random number between 0 and max */
	num = 1 + (int)((double)(max-1) * rand() / (RAND_MAX + 1.0));

	/* Whichever record matches the random number is first; the rest are random */
	for (node = rrlist->head; node; node = node->next)
	{
		if (node->rrtype != DNS_RRTYPE_RR)
			continue;

		if (RR_IS_ADDR(node))
		{
			if (num >= node->lb_low && num <= node->lb_high)
				node->sort = 0;
			else
				node->sort = 1 + (int)(10000.0 * rand() / (RAND_MAX + 1.0));
		}
		else
			node->sort = 10000 + ((MYDNS_RR *)node->rr)->aux;
	}
}
/*--- load_balance() ----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	SORT_ADDRESSES
	If the request is for 'A' or 'AAAA' and there are multiple A or AAAA records, sort them.
	Since this is an A or AAAA record, the answer section contains only addresses.
	If any of the RR's have nonzero "aux" values, do load balancing, else do round robin.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
sort_addresses(t, rrlist)
	TASK *t;
	RRLIST *rrlist;
{
	register RR *node;

	/* If any addresses have nonzero 'aux' values, do load balancing */
	if (rrlist->highest_addr_aux > 0)
		load_balance(t, rrlist);
	else /* Round robin - for address records, set 'sort' to a random number 0-1000 */
	{
		for (node = rrlist->head; node; node = node->next)
		{
			if (node->rrtype != DNS_RRTYPE_RR)
				continue;
			if (RR_IS_ADDR(node))
				node->sort = (int)(10000.0 * rand() / (RAND_MAX + 1.0));
			else
				node->sort = 10000 + ((MYDNS_RR *)node->rr)->aux;
		}
	}

	/* Do the sort */
	rrlist->head = rrlist_sort(rrlist->head);

	/* Redetermine list tail */
	for (node = rrlist->head; node; node = node->next)
		if (!node->next)
			rrlist->tail = node;
}
/*--- sort_addresses() --------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	SORT_MX
	When there are multiple equal-preference MX records, randomize them to help keep the load
	equal.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
sort_mx(t, rrlist)
	TASK *t;
	RRLIST *rrlist;
{
	register RR *node;

	/* Set 'sort' to a random number */
	for (node = rrlist->head; node; node = node->next)
	{
		if (node->rrtype != DNS_RRTYPE_RR)
			continue;
		if (RR_IS_MX(node))
			node->sort = (((MYDNS_RR *)node->rr)->aux * 100) + (int)(100.0 * rand() / (RAND_MAX + 1.0));
		else
			node->sort = 100000 + ((MYDNS_RR *)node->rr)->aux;
	}

	/* Do the sort */
	rrlist->head = rrlist_sort(rrlist->head);

	/* Redetermine list tail */
	for (node = rrlist->head; node; node = node->next)
		if (!node->next)
			rrlist->tail = node;
}
/*--- sort_mx() ---------------------------------------------------------------------------------*/

/* vi:set ts=3: */
